package uk.co.q3c.deplan.client.domain.dag;

/*
 * Copyright The Codehaus Foundation.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may
 * obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions
 * and limitations under the License.
 */
/**
 * 07 July 2010 Modified by David Sowerby to make generic, and track changes. Clone removed
 */

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import javax.persistence.Id;
import javax.persistence.Transient;

import com.googlecode.objectify.Key;
import com.googlecode.objectify.annotation.Cached;
import com.googlecode.objectify.annotation.Serialized;
import com.googlecode.objectify.annotation.Unindexed;

/**
 * DAG = Directed Acyclic Graph
 * 
 * @author <a href="michal.maczka@dimatics.com">Michal Maczka</a>
 * @version $Id: DAG.java 8010 2009-01-07 12:59:50Z vsiveton $
 * @todo this class should be reanmed from DAG to Dag
 */
@Unindexed
@Cached(expirationSeconds = 600)
public class DAG<T> implements Serializable, SharedStructure {
	private static Logger logger = Logger.getLogger(DAG.class.getName());
	private String name;
	private static final long serialVersionUID = 1L;
	private int version;
	@Transient
	private SharedStructureChangeLog changeLog;
	/**
	 * Nodes will be kept in two data structures at the same time for faster processing
	 */
	/**
	 * Maps vertex's label to vertex
	 */
	@Serialized
	private Map<T, Vertex<T>> vertexMap = new HashMap<T, Vertex<T>>();

	/**
	 * Contain list of all vertices
	 */
	@Serialized
	private List<Vertex<T>> vertexList = new ArrayList<Vertex<T>>();
	// @Transient

	@Id
	private Long keyId;

	// ------------------------------------------------------------
	// Constructors
	// ------------------------------------------------------------

	/**
     *
     */
	public DAG() {
		super();
	}

	// ------------------------------------------------------------
	// Accessors
	// ------------------------------------------------------------

	/**
	 * @return
	 */
	public List<Vertex<T>> getVerticies() {
		return vertexList;
	}

	public Set<T> getLabels() {
		return vertexMap.keySet();
	}

	// ------------------------------------------------------------
	// Implementation
	// ------------------------------------------------------------

	/**
	 * Adds vertex to DAG. If vertex of given key already exist in DAG no vertex is added
	 * 
	 * @param label
	 *            The lable of the Vertex<T>
	 * @return New vertex if vertext of given label was not presenst in the DAG or exising vertex if vertex of given labale was alredy added
	 *         to DAG
	 */
	public Vertex<T> addVertex(T key) {
		Vertex<T> retValue = null;
		// check if vertex is already in DAG
		if (vertexMap.containsKey(key)) {
			retValue = vertexMap.get(key);
		} else {
			retValue = new Vertex<T>(key);

			vertexMap.put(key, retValue);

			vertexList.add(retValue);
			changeLog.add(new DAGVertexChange<T>(true, key));
		}

		return retValue;
	}

	public void addEdge(final T from, final T to) throws CycleDetectedException, ChangeInvalidException {
		final Vertex<T> v1 = getVertex(from);
		final Vertex<T> v2 = getVertex(to);
		addEdge(v1, v2);
	}

	protected void addEdge(final Vertex<T> from, final Vertex<T> to) throws CycleDetectedException, ChangeInvalidException {

		if ((from == null) || (to == null)) {
			if (changeLog.isSuspended()) {
				throw new ChangeInvalidException();
			}
			if (logger.isLoggable(Level.SEVERE)) {
				logger.severe("Task must be added to the DAG when task is first saved");
			}
		}
		from.addEdgeTo(to);
		to.addEdgeFrom(from);
		final List<T> cycle = new CycleDetector<T>().introducesCycle(to);
		if (cycle != null) {
			// remove edge which introduced cycle
			removeEdge(from, to);
			final String msg = "Edge between '" + from + "' and '" + to + "' introduces to cycle in the graph";
			throw new CycleDetectedException(msg, cycle);
		}
		changeLog.add(new DAGEdgeChange<T>(true, from.getKey(), to.getKey()));
	}

	public boolean removeEdge(final T from, final T to) {
		final Vertex<T> v1 = getVertex(from);
		final Vertex<T> v2 = getVertex(to);
		return removeEdge(v1, v2);
	}

	public boolean removeEdge(final Vertex<T> from, final Vertex<T> to) {
		if ((from == null) || (to == null)) {
			if (changeLog.isSuspended()) {
				return false;
			}
			if (logger.isLoggable(Level.SEVERE)) {
				logger.severe("Task must be added to the DAG when task is first saved");
				return false;
			}
		}
		boolean rf = from.removeEdgeTo(to);
		boolean rt = to.removeEdgeFrom(from);
		boolean changed = rf || rt;
		if (changed) {
			changeLog.add(new DAGEdgeChange<T>(false, from.getKey(), to.getKey()));
		}
		return changed;
	}

	public Vertex<T> getVertex(final T label) {
		return vertexMap.get(label);
	}

	public boolean hasEdge(final T key1, final T key2) {
		final Vertex<T> v1 = getVertex(key1);

		final Vertex<T> v2 = getVertex(key2);

		final boolean retValue = v1.getChildren()
				.contains(v2);

		return retValue;

	}

	/**
	 * Indicates if there is at least one edge leading to or from vertex of given label
	 * 
	 * @return <code>true</true> if this vertex is connected with other vertex,<code>false</code> otherwise
	 */
	public boolean isConnected(final T key) {
		final Vertex<T> vertex = getVertex(key);
		final boolean retValue = vertex.isConnected();
		return retValue;

	}

	/**
	 * Return the list of labels of successor in order decided by topological sort
	 * 
	 * @param key
	 *            The label of the vertex whose predessors are serched
	 * 
	 * @return The list of labels. Returned list contains also the label passed as parameter to this method. This label should always be the
	 *         last item in the list.
	 */
	public List<T> getSuccessorLabels(final T key) {
		final Vertex<T> vertex = getVertex(key);

		final List<T> retValue;

		// optimization.
		if (vertex.isLeaf()) {
			retValue = new ArrayList<T>(1);

			retValue.add(key);
		} else {
			retValue = TopologicalSorter.sort(vertex);
		}

		return retValue;
	}

	public SharedStructureChangeLog getChangeLog() {
		return changeLog;
	}

	public void removeVertex(T key) {
		Vertex<T> v = getVertex(key);
		// remove from Dag lists
		vertexMap.remove(v);
		vertexList.remove(v);
		// remove any edges connected to this vertex
		removeAllEdgesFrom(v);

		// record the change
		changeLog.add(new DAGVertexChange<T>(false, v.getKey()));
	}

	/**
	 * remove all predecessor and successor connections from the node specified by <code>key</code> but leaves the node itself in place
	 * 
	 * @param key
	 */
	public void removeAllConnnections(T key) {
		Vertex<T> v = getVertex(key);
		removeAllEdgesFrom(v);
	}

	public void removeAllEdgesFrom(Vertex<T> v) {
		ArrayList<Vertex<T>> parents = new ArrayList<Vertex<T>>(v.getParents());
		for (Vertex<T> parent : parents) {
			removeEdge(parent, v);
		}
		ArrayList<Vertex<T>> children = new ArrayList<Vertex<T>>((v.getChildren()));
		for (Vertex<T> child : children) {
			removeEdge(v, child);
		}
	}

	@Override
	public int getVersion() {
		return version;
	}

	@Override
	public void incrementVersion() {
		version++;
	}

	@Override
	public void setChangeLog(SharedStructureChangeLog changes) {
		this.changeLog = changes;
	}

	public Long getKeyId() {
		return keyId;
	}

	public void setKeyId(Long id) {
		this.keyId = id;
	}

	public void setVersion(int version) {
		this.version = version;
	}

	public boolean hasChanged() {
		return changeLog.changeCount() > 0;
	}

	public List<Vertex<T>> getSuccessors(T baseKey) {
		Vertex<T> vertex = getVertex(baseKey);
		if (baseKey == null) {
			if (logger.isLoggable(Level.WARNING)) {
				logger.warning("Cannot look up a null value in " + getName());
			}
			return new ArrayList<Vertex<T>>();
		}
		if (vertex == null) {
			if (logger.isLoggable(Level.WARNING)) {
				logger.warning("Node not found in " + getName() + "for " + baseKey.toString());
			}
			return new ArrayList<Vertex<T>>();
		}
		return vertex.getChildren();

	}

	public List<Vertex<T>> getPredecessors(T baseKey) {
		Vertex<T> vertex = getVertex(baseKey);
		return vertex.getParents();

	}

	@SuppressWarnings("unchecked")
	@Override
	public void applyChanges() {
		changeLog.suspendLogging();
		List<SharedStructureChange> changes = changeLog.getChanges();
		for (SharedStructureChange change : changes) {
			if (change instanceof DAGVertexChange<?>) {
				DAGVertexChange<T> dvc = (DAGVertexChange<T>) change;
				if (change.isAdd()) {
					addVertex(dvc.getKey());
					dvc.setApplied(true);
				} else {
					removeVertex(dvc.getKey());
					dvc.setApplied(true);
				}
			} else {
				DAGEdgeChange<T> dec = (DAGEdgeChange<T>) change;
				if (change.isAdd()) {
					try {
						addEdge(dec.getFrom(), dec.getTo());
						dec.setApplied(true);
					} catch (Exception e) {
						dec.setApplied(false);
					}
				} else {
					removeEdge(dec.getFrom(), dec.getTo());
					dec.setApplied(true);
				}
			}
		}
		changeLog.resumeLogging();
	}

	public boolean nodeHasPredecessor(T nodeKey, T predecessorKey) {
		Vertex<T> v = getVertex(nodeKey);
		boolean result = v.hasParent(predecessorKey);
		return result;
	}

	public boolean nodeHasSuccessor(T nodeKey, T successorKey) {
		Vertex<T> v = getVertex(nodeKey);
		return v.hasChild(successorKey);
	}

	public String debugOutput() {
		StringBuilder buf = new StringBuilder();
		buf.append("Object counts are: \n");
		buf.append("\tMap count: " + vertexMap.size() + "\n");
		buf.append("\tList count: " + vertexList.size() + "\n");
		buf.append("\tChange count: " + changeLog.changeCount() + "\n");
		return buf.toString();
	}

	public int changeCount() {
		return changeLog.changeCount();
	}

	@Override
	public void clearChanges() {
		changeLog.clear();
	}

	@Override
	public boolean hasChanges() {
		return changeCount() > 0;
	}

	@Override
	public String getName() {
		return name;
	}

	@Override
	public void setName(String name) {
		this.name = name;
	}

	@SuppressWarnings("unchecked")
	public Key<DAG<T>> getKey() {
		return new Key<DAG<T>>((Class<? extends DAG<T>>) DAG.class, keyId);
	}

}
